//
//  ILGAlgorithmModule.m
//  ILGDemo
//
//  Created by happy on 2020/3/11.
//  Copyright © 2020 Happy. All rights reserved.
//

#import "ILGAlgorithmModule.h"

@interface ILGMeetingModel : NSObject
@property (nonatomic, assign) NSInteger startTime;
@property (nonatomic, assign) NSInteger endTime;
@end

@implementation ILGMeetingModel
+ (instancetype)defaultInstance:(NSInteger)startTime endTime:(NSInteger)endTime
{
    ILGMeetingModel *model = [ILGMeetingModel new];
    model.startTime = startTime;
    model.endTime = endTime;
    return model;
}
@end


@implementation ILGAlgorithmModule

- (void)performTestMethod
{
//    [self countNumberForMeetingRoom];
//    NSString *subStr = [self maxLengthUnrepeatSubString:@"abcdabf"];
//    int sum = [self sumByRecursionFrom:5 to:2];
    algorithmForRank();
    
    int array[9] = {1,2,8,6,9,5,7,3,4};
    int tmpArray[9] = {0};
    int addNumber = 0, evenNumber = 0;
    for (int i = 0; i < 9; i++) {
        if (array[i]%2 == 0) {
            evenNumber+=1;
            tmpArray[evenNumber*2 - 1] = array[i];
        } else {
            addNumber+=1;
            tmpArray[addNumber*2 - 2] = array[i];
        }
    }
    
    for (int i = 0; i < 9; i++) {
        printf("tmpArray[%d] = %d \n", i, tmpArray[i]);
    }
}

- (int)sumByRecursionFrom:(int)fromValue to:(int)toValue
{
    if (fromValue > toValue) {
        fromValue = fromValue ^ toValue;
        toValue = fromValue ^ toValue;
        fromValue = fromValue ^ toValue;
    }
    
    if (fromValue == toValue) {
        return toValue;
    } else if (toValue - fromValue == 1) {
        return fromValue + toValue;
    } else {
        return fromValue + toValue + [self sumByRecursionFrom:fromValue+1 to:toValue-1];
    }
}

- (NSString *)maxLengthUnrepeatSubString:(NSString *)string
{
    int maxStart = 0;
    int maxLength = 0;
    int length = 0;
    int start = 0;
    NSMutableDictionary *positionDic = [NSMutableDictionary dictionary];
    
    for (int index = 0; index < string.length; index++) {
        NSString *key = [NSString stringWithFormat:@"%c", [string characterAtIndex:index]];
        
        if (positionDic[key]) {
            int lastPosition = [positionDic[key] intValue];
            if (lastPosition >= start) {
                if (maxLength < length) {
                    maxStart = start;
                    maxLength = length;
                }
                
                length = index - lastPosition;
                start = lastPosition + 1;
            }
            
        } else {
            length++;
        }
        
        positionDic[key] = @(index);
        
        if (index == string.length - 1 && maxLength < length) {
            maxStart = start;
            maxLength = length;
        }
    }
    
    NSString *resultStr = [string substringWithRange:NSMakeRange(maxStart, maxLength)];
    return resultStr;
}

- (void)countNumberForMeetingRoom
{
    NSMutableArray *array = [@[[ILGMeetingModel defaultInstance:0 endTime:2],//x1q
                       [ILGMeetingModel defaultInstance:1 endTime:3],//x2w
                       [ILGMeetingModel defaultInstance:2 endTime:4],//x1q
                       [ILGMeetingModel defaultInstance:3 endTime:4],//x2w
                       [ILGMeetingModel defaultInstance:3 endTime:5],//x3e
                       [ILGMeetingModel defaultInstance:4 endTime:6],//x1q
                       [ILGMeetingModel defaultInstance:5 endTime:8],//x2w
                       [ILGMeetingModel defaultInstance:8 endTime:10],//x1q
                       [ILGMeetingModel defaultInstance:9 endTime:10],//x2w
                       [ILGMeetingModel defaultInstance:10 endTime:12],//x1q
                       [ILGMeetingModel defaultInstance:10 endTime:12],//x2w
                       [ILGMeetingModel defaultInstance:11 endTime:15],//x3e
                       [ILGMeetingModel defaultInstance:12 endTime:22],//x1q
                       [ILGMeetingModel defaultInstance:13 endTime:21],//x2w
                       [ILGMeetingModel defaultInstance:18 endTime:22],//x3e
                       [ILGMeetingModel defaultInstance:22 endTime:24]] mutableCopy]; // 1q result = 4
    
    NSMutableArray *resultArr = [NSMutableArray array];
    
    for (int i = 0; i < array.count; i++) {
        ILGMeetingModel *modelI = array[i];
        
        NSInteger minus = 24;
        int k;
        for (k = 0; k < resultArr.count; k++) {
            ILGMeetingModel *modelK = resultArr[k];
            
            if (modelI.startTime >= modelK.endTime && minus > modelI.startTime - modelK.endTime) {
                minus = modelI.startTime - modelK.endTime;
                break;
            }
        }
        
        if (k == resultArr.count) {
            [resultArr addObject:modelI];
        } else {
            [resultArr replaceObjectAtIndex:k withObject:modelI];
        }
    }
    
    NSInteger roomNumber = resultArr.count;

}

- (void)countNumberForMeetingRoom2
{
    NSMutableArray *array = [@[[ILGMeetingModel defaultInstance:0 endTime:2],//x1q
                       [ILGMeetingModel defaultInstance:1 endTime:3],//x2w
                       [ILGMeetingModel defaultInstance:2 endTime:4],//x1q
                       [ILGMeetingModel defaultInstance:3 endTime:4],//x2w
                       [ILGMeetingModel defaultInstance:3 endTime:5],//x3e
                       [ILGMeetingModel defaultInstance:4 endTime:6],//x1q
                       [ILGMeetingModel defaultInstance:5 endTime:8],//x2w
                       [ILGMeetingModel defaultInstance:8 endTime:10],//x1q
                       [ILGMeetingModel defaultInstance:9 endTime:10],//x2w
                       [ILGMeetingModel defaultInstance:10 endTime:12],//x1q
                       [ILGMeetingModel defaultInstance:0 endTime:22],//x2
                       [ILGMeetingModel defaultInstance:11 endTime:15],//x3w
                       [ILGMeetingModel defaultInstance:12 endTime:22],//x1q
                       [ILGMeetingModel defaultInstance:13 endTime:21],//x2e
                       [ILGMeetingModel defaultInstance:18 endTime:22],//x3w
                       [ILGMeetingModel defaultInstance:22 endTime:24]] mutableCopy]; // 1q result = 4
    
    NSMutableArray *resultArr = [NSMutableArray array];
    
    for (int i = 0; i < array.count; i++) {
        ILGMeetingModel *modelI = array[i];
        
        NSInteger minus = 24;
        int k;
        for (k = 0; k < resultArr.count; k++) {
            NSMutableArray *subArr = resultArr[k];
            ILGMeetingModel *modelK = subArr.lastObject;
            
            if (modelI.startTime >= modelK.endTime && minus > modelI.startTime - modelK.endTime) {
                minus = modelI.startTime - modelK.endTime;
                break;
            }
        }
        
        if (k == resultArr.count) {
            [resultArr addObject:[NSMutableArray array]];
        }
        
        NSMutableArray *subArrTmp = resultArr[k];
        [subArrTmp addObject:modelI];
    }
    
    NSInteger roomNumber = resultArr.count;

}


- (NSArray *)findViews:(UIView *)targetView {
    NSMutableArray *resultArr = [NSMutableArray array];
    
    if ([targetView isMemberOfClass:[UIView class]]) {
        [resultArr addObject:targetView];
    }
    
    NSMutableArray *findArr = [NSMutableArray arrayWithArray:targetView.subviews];
    while (findArr.count) {
        UIView *targetView = findArr.firstObject;
        
        if ([targetView isMemberOfClass:[UIView class]]) {
            [resultArr addObject:targetView];
            continue;
        }
        
        [targetView.subviews enumerateObjectsUsingBlock:^(__kindof UIView * _Nonnull obj, NSUInteger idx, BOOL * _Nonnull stop) {
            if ([obj isMemberOfClass:[UIView class]]) {
                [resultArr addObject:obj];
            } else if (obj.subviews) {
                [findArr addObject:obj];
            }
        }];
        
        [findArr removeObjectAtIndex:0];
    }
    
    return resultArr;
}


- (NSArray *)findButtonsByRecursion:(UIView *)targetView {
    NSMutableArray *resultArr = [NSMutableArray array];
    
    if ([targetView isMemberOfClass:[UIButton class]]) {
        [resultArr addObject:targetView];
        
        return resultArr;
    }
    
    [targetView.subviews enumerateObjectsUsingBlock:^(__kindof UIView * _Nonnull obj, NSUInteger idx, BOOL * _Nonnull stop) {
        if ([obj isMemberOfClass:[UIButton class]]) {
            [resultArr addObject:obj];
        } else if (obj.subviews) {
            [resultArr addObjectsFromArray:[self findButtonsByRecursion:obj]];
        }
    }];
    
    return resultArr;
}

NSArray* findButtons(UIView *targetView) {
    NSMutableArray *resultArr = [NSMutableArray array];
    
    if ([targetView isMemberOfClass:[UIButton class]]) {
        [resultArr addObject:targetView];
        return resultArr;
    }
    
    NSMutableArray *mutArr = [NSMutableArray arrayWithArray:targetView.subviews];
    while (mutArr.count) {
        UIView *targetView = mutArr.firstObject;
        
        if ([targetView isMemberOfClass:[UIButton class]]) {
            [resultArr addObject:targetView];
            continue;
        }
        
        [targetView.subviews enumerateObjectsUsingBlock:^(__kindof UIView * _Nonnull obj, NSUInteger idx, BOOL * _Nonnull stop) {
            if ([obj isMemberOfClass:[UIButton class]]) {
                [resultArr addObject:obj];
            } else if (obj.subviews) {
                [mutArr addObject:obj];
            }
        }];
        
        [mutArr removeObjectAtIndex:0];
    }
    
    return resultArr;
}


# pragma mark - C语言

void performAlgorithm()
{
    int array[10] = {-1};
    for (int i = 0; i< 10; i++) {
        printf("value at index %d = %d", i, array[i]);
    }
}


# pragma mark - 算法
# pragma mark 排序

void algorithmForRank()
{
    int array[] = {24,99,2,4,7,1,3,5,8,0,9,6,12, 19,11,56,29};
    
    int arrayCount = 0;
    if (sizeof(array)) {
        arrayCount = sizeof(array)/sizeof(array[0]);
    }
    
//    bubble_sort(array, arrayCount);
//    insert_sort(array, arrayCount);
    sort_quick(array, 0, arrayCount-1);
    
    printf("\n");
    for (int i = 0; i < arrayCount; i++) {
        printf("%d ", array[i]);
    }
    printf("\n");
}

void sort_quick(int a[], int left, int right)
{
    int low = left, hight = right;
    if (left < right) {
        int tmp = a[left];
        
        while (left < right) {
            while (left < right && a[right] <= tmp) {
                right--;
            }
            a[left] = a[right];
            
            while (left < right && a[left] >= tmp) {
                left++;
            }
            a[right] = a[left];
        }
        
        a[left] = tmp;
        
        sort_quick(a, low, left - 1);
        sort_quick(a, left+1, hight);
    }
    
}

void sort_select(int *array, int arrayCount)
{
    for (int i = 0; i < arrayCount - 1; i++) {
        
        int positionIndex = i;
        for (int j = i + 1; j < arrayCount; j++) {
            if (array[j] > array[positionIndex]) {
                positionIndex = j;
            }
        }
        
        if (positionIndex > i) {
            array[i] = array[i] - array[positionIndex];
            array[positionIndex] = array[positionIndex] + array[i];
            array[i] = array[positionIndex] - array[i];
        }
    }
}

void sort_bubble(int *array, int arrayCount)
{
    bool isFinish = false;
    
    for (int i = arrayCount - 1; !isFinish && i > 0; i--) {
        
        isFinish = true;
        
        for (int j = 0; j < i; j++) {
            if (array[j] > array[j+1]) {
                array[j] = array[j] - array[j+1];
                array[j+1] = array[j+1] + array[j];
                array[j] = array[j+1] - array[j];
                
                isFinish = false;
            }
        }
    }
}

void sort_insert(int *array, int arrayCount)
{
    for (int i = 1; i < arrayCount ; i++) {
        if (_compare_two_numer(array[i], array[i-1])) {
            int j = i - 1;
            
            while(j >= 0 && _compare_two_numer(array[j+1], array[j])) {
                array[j] = array[j] - array[j+1];
                array[j+1] = array[j+1] + array[j];
                array[j] = array[j+1] - array[j];
                j--;
            }
        }
        
        printf("\n");
        for (int i = 0; i < arrayCount; i++) {
            printf("%d ", array[i]);
        }
        printf("\n");
    }
}

// 数组排序，奇数在左，偶数在右
void sort_oddNumberInLeft_evenNumberInRight()
{
    int array[] = {2, 3, 4, 5, 6, 7, 8, 9};
    
    int left = 0, right = 7;
    
    while (left < right) {
        while ((array[left] & 1) == 1 && left < right) {
            left++;
        }
        
        while ((array[right] & 1) == 0 && right > left) {
            right--;
        }
        
        if (left < right) {
            int tmp = array[left];
            array[left] = array[right];
            array[right] = tmp;
            
            left++;
            right--;
        }
    }
    
    
    for (int i = 0; i < 8; i++) {
        NSLog(@"%d", array[i]);
    }
}

bool _compare_two_numer(int a, int b)
{
    if (a > b) {
        return YES;
    } else {
        return NO;
    }
}

// 不用第三参数，交换两个数
void swap(int *left, int *right)
{
    int *tmp = left;
    left = right;
    right = tmp;
}

#pragma mark 其它算法
// 判断素数(只能被1和本身整除)
bool isPrimeNumer(int number)
{
    bool resultValue = YES;
    if (number <= 3) {
        return resultValue;
    }
    
    for (int i = 2; i <= sqrt(number); i++) {
        if (number%i == 0) {
            resultValue = NO;
            break;
        }
    }
    
    return resultValue;
}

// 判断闰年
bool isLeapYear(int year)
{
    BOOL resultValue = NO;
    
    if (year % 4 == 0) {
        if (year % 100 == 0) {
            if (year % 400 == 0) {
                resultValue = YES;
            }
        } else {
            resultValue = YES;
        }
    }
    
    return resultValue;
}


@end
